#pragma once


//需要仿函数的出现用来解决make_pair<string,int>等类型不能直接转换成整型数据的
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}

};
//如果是string类型的单独处理
//特化处理
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		int Hashi = 0;
		for (auto e : s)
		{
			Hashi *= 131;
			Hashi += e;
		}
		return Hashi;
	}
};

namespace Hashorder {
	enum State
	{
		EXIST,
		EMPTY,
		DELETE,
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _st = EMPTY;
	};
	template<class K, class V, class Hash = HashFunc<K>>
	class Hash_table {
		typedef  HashData<K, V> Data;
	public:
		Hash_table()
			:_n(0)
		{
			_table.resize(10); //初始化一下，免得最开始的没有size
		}
		bool insert(const pair<K, V>& kv)
		{
			//如果插入相同的数据直返回false
			if (Find(kv.first))
				return false;
			//在插入数据之前，应该需要先判断一下是否需要扩容
			//负载因子 = n/_table.size()
			if (_n * 10 / _table.size() > 7)
			{
				//不能直接复制下去，需要建立一个新表，从头开始
				Hash_table<K, V, Hash> ht;
				ht._table.resize(_table.size() * 2);
				//从旧表取数据插入新表
				for (auto& e : _table)
				{
					if (e._st == EXIST)
					{
						ht.insert(e._kv);
					}
				}
				_table.swap(ht._table);
			}

			int hashi = Hash()(kv.first) % _table.size();
			while (_table[hashi]._st == EXIST)
			{
				++hashi;
				hashi %= _table.size();
			}
			_table[hashi]._kv = kv;
			_table[hashi]._st = EXIST;
			_n++;
			return true;
		}
		Data* Find(const K& key)
		{
			int hashi = Hash()(key) % _table.size();
			while (_table[hashi]._st != EMPTY)
			{
				if (_table[hashi]._st != DELETE && _table[hashi]._kv.first == key)
				{
					return &_table[hashi];
				}
				else
				{
					++hashi;
					hashi %= _table.size();
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Data* erasedata = Find(key);
			if (erasedata)
			{
				erasedata->_st = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<Data> _table;
		size_t _n = 0; //表中数据

	};
	void Test1()
	{
		Hash_table<int, int> ht;
		int a[] = { 27,7,28,30,41,55,44 , 37,38,20,21,22 };
		for (auto e : a)
		{
			ht.insert(make_pair(e, e));
		}
		cout << ht.Find(28) << endl;
		cout << ht.Find(30) << endl;
		ht.Erase(28);
		cout << ht.Find(28) << endl;
		cout << ht.Find(30) << endl;
	}
	//对于字符串的数据而言
	//kv.first求余此时就失去效果了
	//此时需要把字符串转换成int类型的数据进行插入表中
	//此时就用到了仿函数
	void Teststring()
	{
		string arr[] = { "苹果","香蕉","草莓","菠萝","苹果","香蕉","草莓","苹果","香蕉","草莓","苹果","香蕉","苹果","苹果" };
		Hash_table<string, int> HString;

		for (auto e : arr)
		{
			if (HString.Find(e))
			{
				HString.Find(e)->_kv.second++;
			}
			else
			{
				HString.insert(make_pair(e, 1));
			}
		}
		HashFunc<string> hf;
		cout << hf("草莓") << endl;
		cout << hf("菠萝") << endl;
		cout << hf("香蕉") << endl;
		cout << hf("苹果") << endl;
	}

}


namespace bucketHash {

	template<class K,class V>
	struct HashNode {
		pair<K, V> _kv;
		HashNode<K, V>* _next;
		HashNode(const pair<K,V>& kv)
			:_next(nullptr)
			,_kv(kv)  
		{}
	};

	template<class K,class V,class Hash=HashFunc<K>>
	class HashBucket {
		typedef HashNode<K, V> Node;
	public:
		HashBucket()
			:_n(0)
		{
			_table.resize(10, nullptr);
		}
		//需要调用析构函数
		//内置类型不做处理，自定义类型调用自己的析构函数
		//
		~HashBucket()
		{
			//for (size_t i = 0; i < _table.size(); ++i)
			//{
			//	Node* cur = _table[i];
			//	Node* prev = nullptr;
			//	while (cur)
			//	{
			//		prev = cur;
			//		delete cur;
			//		cur = prev->_next;
			//	}
			//}
			_table.resize(0);
		}
		bool insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;
			//扩容，当负载因子为1的时候
			if (_n == _table.size())
			{
				//这时候为了节省new节点的空间，选择重复利用挂在旧表上的节点
				//直接new 一个新的table出来即可
				vector<Node*> NewTable;
				NewTable.resize(_table.size() * 2, nullptr);
				//把旧表的节点链接在新表上
				for (size_t i = 0; i < _table.size(); ++i)
				{
					if (i == 8)
					{
						cout << endl;
					}
					Node* cur = _table[i];
					Node* prev = nullptr;
					while (cur)
					{
						prev = cur->_next;
						int hashi = Hash()(cur->_kv.first) % NewTable.size();
						Node* next = NewTable[hashi];
						cur->_next = next;
						NewTable[hashi] = cur;
						cur = prev;
					}
				}
				//交换新表旧表
				_table.swap(NewTable);
			}

			//跟表一样首先需要计算hashi
			size_t hashi = Hash()(kv.first) % _table.size();
			//选择头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;
			return true;

		}
		Node* Find(const K& key)
		{
			size_t hashi = Hash()(key) % _table.size();

			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			int hashi = Hash()(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					//假设第一个就是要查找的对象
					if (_table[hashi]->_kv.first == key)
					{
						prev = cur->_next;
						delete cur;
						_table[hashi] = prev;
					}
					else
					{
						prev->_next = cur->_next;
						delete cur;
						cur = nullptr;
					}
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<Node*> _table;    //指针数组
		size_t _n=0 ;
	};


	void Test1()
	{
		HashBucket<int, int> hb;
		int a[] = { 27,7,28,30,41,55,44 , 37,38 };
		for (auto e : a)
		{
			hb.insert(make_pair(e, e));
		}
		hb.insert(make_pair(18, 18));
		hb.insert(make_pair(33, 33));
		cout<<hb.Erase(38);
		cout<<hb.Erase(18);
	}
	void Teststring()
	{
		string arr[] = { "苹果","香蕉","草莓","菠萝","苹果","香蕉","草莓","苹果","香蕉","草莓","苹果","香蕉","苹果","苹果" };
		HashBucket<string, int> HString;

		for (auto e : arr)
		{
			if (HString.Find(e))
			{
				HString.Find(e)->_kv.second++;
			}
			else
			{
				HString.insert(make_pair(e, 1));
			}
		}
		HashFunc<string> hf;
		cout << hf("草莓") << endl;
		cout << hf("菠萝") << endl;
		cout << hf("香蕉") << endl;
		cout << hf("苹果") << endl;	}
}
